# 输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。
# 例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。
#
# 来源：力扣（LeetCode）
# 链接：https://leetcode.cn/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof

# 输入：n = 12
# 输出：5


class Solution:
    def countDigitOne(self, n: int) -> int:
        res = 0
        bit = 1
        while bit <= n:
            cur = (n // bit) % 10
            high = n // bit // 10
            low = n % bit

            if cur > 1:
                res += (high + 1) * bit
            elif cur == 1:
                res += high * bit + 1 + low
            else:
                res += high * bit

            bit *= 10
        return res
